package com.hspedu.newData.每日一题;

import org.junit.Test;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-06 
 * @Version: 1.0
 */

public class LC790多米诺和托米洛平铺 {

    private static int mod = 10000007;

    public int numTilings(int n) {

        int[][] dp = new int[n][4];
        dp[0][3] = 1;
        dp[0][0] = 1;

//        dp[i][0] 表示第i列为空的情况
//        dp[i][1] 表示第i列下方为空的情况
//        dp[i][2] 表示第i列上方为空的情况
//        dp[i][3] 表示第i列为满的情况

        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][3];
            dp[i][1] = (dp[i-1][0] + dp[i-1][2])%mod;
            dp[i][2] = (dp[i-1][0] + dp[i-1][1])%mod;
            dp[i][3] = ((((dp[i-1][0] + dp[i-1][3])%mod + dp[i-1][1])%mod) + dp[i-1][2])%mod;
        }

        return dp[n-1][3];

    }

    @Test
    public void test() {
        // 测试代码

        int i = numTilings(5);
        System.out.println("=======");
    }

}
